package pro.softzhang.algo.lc500;

import pro.softzhang.algo.common.TreeNode;
import pro.softzhang.algo.flag.knowledge.KBinaryTree;

import java.util.Stack;

@KBinaryTree
public class LC538_ConvertBstToGreaterTree {
    public static void main(String[] args) {

    }

    static
    class Solution {
        public TreeNode convertBST(TreeNode root) {
            Stack<TreeNode> stack = new Stack();
            TreeNode current = root;
            int sum = 0;
            while (current != null || !stack.isEmpty()) {
                while (current != null) {
                    stack.push(current);
                    current = current.right;
                }
                current = stack.pop();
                sum += current.val;
                current.val = sum;
                current = current.left;
            }
            return root;
        }
    }

    static
    class Solution1 {
        int total = 0;
        public TreeNode convertBST(TreeNode root) {
            if (root == null) return null;

            convertBST(root.right);

            root.val = root.val + total;
            total = root.val;

            convertBST(root.left);
            return root;
        }
    }
}